/**
 * Written By: MinHo Kim (minho.kim.korea@gmail.com)
 * Copyright (C) 2011, MinHo Kim, Software Expert Program, KAIST University, Seoul, Korea.
 * This program is free software; you can redistribute it and/or modify it 
 * under the terms of the GNU General Public License as published 
 * by the Free Software Foundation; version 2 of the License.
 * This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; 
 * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  
 * See the GNU General Public License for more details.
 */
package kaist.sep502.tsp.controller;

import java.util.PriorityQueue;

import kaist.sep502.tsp.algorithm.heuristic.Heuristic;
import kaist.sep502.tsp.model.CityPath;
import kaist.sep502.tsp.model.Problem;

/**
 * @author minho kim
 *
 */
public class UniformCostSearch extends SearchAlgorithm {
	private PriorityQueue<CityPath> frontier;
	
	public Solution search(){
		solution.expandedNodeCount = 0;
		solution.startStopWatch();
		
		// 1. 초기화 : Frontier 생성/초기화, Explored 생성/초기화, 알고리즘 선
		frontier = new PriorityQueue<CityPath>(2000000);  // TODO : Frontier 초기 크기 계산 방법
		CityPath cityPath = new CityPath(Problem.getDepartureCityNo());
		frontier.add(cityPath);
		
		// 2. 검색 처리 : goal 체크,
		while(true){
			solution.expandedNodeCount++;
			
			// 2.1 더 이상 탐색할 도시가 없으면 검색 실패 
			if(frontier.isEmpty()){
				solution.stopStopWatch();
				solution.setSuccess(false);
				return solution;
			}
			
			// 2.2 하나의 탐색 대상 도시를 꺼냄 
			cityPath = frontier.poll();
			
			// 2.3 Goal인지 체크하고 맞다면 솔루션을 리턴한다.
			if(Problem.checkGoal(cityPath)){
				solution.setGoalCityPath(cityPath);
				solution.setSuccess(true);
				solution.stopStopWatch();
				return solution;
			}
			
			// 2.4 주변 도시를 찾아서 검색 대상 목록(Frontier)에 추가한다.
			handleFrontier(cityPath);
		}
	}

	public void handleFrontier(CityPath cityPath) {
		int citySize = Problem.getCitySize();
		
		// 마지막 도시까지 다 여행했는지 여부에 따라 처리가 달라짐 
		int tourHistorySize = cityPath.index; 
		if(tourHistorySize == citySize){
			cityPath.set(Problem.getDepartureCityNo(), 0.0);
			frontier.add(cityPath);
			return;
		}
		
		// 마지막 도시까지 여행을 하지 않은 경우 이웃도시를 찾아서 리턴한다.
		Heuristic h = new Heuristic();
		for(int i=0; i < citySize; i++){
			// 이미 들렸던 도시이면 Skip
			boolean didDropBy = false;
			for(int j=0; j < tourHistorySize; j++){
				if(i == cityPath.tourHistory[j]){
					didDropBy = true;
					break;
				}
			}
			
			if(didDropBy){ 
				continue;
			}
			
			CityPath newCityPath = cityPath.clone();
			h = heuristicAlgorithm.getHx(cityPath, i);
			newCityPath.set(h.cityNo, h.hx);
			
			if(frontier.contains(newCityPath)){
				continue;
			}
			
			frontier.add(newCityPath);
		}
	}
}
